package com.mlamp.排序;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {

        int array[] = new int[]{
                2, 5, 8, 1, 3, 100
        };
        int[] ints = mergesort3(array);
        System.out.println(Arrays.toString(ints));

    }

    public static int[] mergesort(int[] array) {
        if (array.length <= 2) return array;
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(mergesort(left), mergesort(right));
    }

    public static int[] mergesort3(int[] array) {
        if (array.length <= 2) return array;
        int len = array.length;
        int mid = len >> 1;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, len);
        return merge4(mergesort3(left), mergesort3(right));
    }


    public static int[] mergesort23(int[] array) {
        if (array.length <= 2) return array;
        int len = array.length;
        int mid = len >> 1;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, len);
        return merge4(mergesort23(left), mergesort23(right));
    }


    private static int[] merge4(int[] mergesort3, int[] mergesort31) {
        int[] result = new int[mergesort3.length + mergesort31.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= mergesort3.length) {
                result[index] = mergesort31[j++];
            } else if (j >= mergesort31.length) {
                result[index] = mergesort3[i++];
            } else if (mergesort3[i] > mergesort31[j]) {
                result[index] = mergesort31[j++];
            } else result[index] = mergesort3[i++];
        }

        return result;
    }


    public static int[] mergeSort2(int[] array) {
        if (array.length <= 2) return array;
        int mid = array.length >> 1;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(mergeSort2(left), mergeSort2(right));
    }


    public static int[] merge2(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int i = 0, index = 0, j = 0; index < result.length; i++) {
            if (i >= left.length) {
                result[index] = right[j++];
            } else if (j >= right.length) {
                result[index] = left[i++];
            } else if (left[i] > right[j]) result[index] = right[j++];
            else result[index] = left[i++];
        }
        return result;
    }


    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= left.length) {
                result[index] = right[j++];
            } else if (j >= right.length) {
                result[index] = left[i++];
            } else if (left[i] > right[j]) {
                result[index] = right[j++];
            } else result[index] = left[i++];
        }
        return result;
    }
}
